package cn.cxq.learning.single_linked_list;

/**
 * 剑指offer
 * 反转链表
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：1160126
 * 本题知识点： 链表
 *  算法知识视频讲解
 * 题目描述
 * 输入一个链表，反转链表后，输出新链表的表头。
 * 示例1
 * 输入
 * {1,2,3}
 * 返回值
 * {3,2,1}
 */
public class ReverseList {

    public ListNode ReverseList(ListNode head) {

        if (head == null) {
            return null;
        }
        // write code here
        ListNode newHead = new ListNode(Integer.MIN_VALUE); // 辅助指针

        ListNode cur = head;
        ListNode after = cur.next;

        while (after!=null) {
            cur.next = newHead.next;
            newHead.next = cur;
            cur = after;
            after = cur.next;
        }

        cur.next = newHead.next;
        newHead.next = cur;

        return newHead.next;
    }
}
